#include <cstdio>
#include <iostream>
#include "liste.hpp"
#include <limits>

using namespace std;

void initListe(Liste & l, void (*fInit)(Elem&, Elem, bool), void(*fAffectation)(Elem&, Elem),
        void (*fAffiche)(const Elem&), int (*fCompare)(const Elem&, const Elem&),
        void (*fTestament)(Elem&)) {
    l.ad = NULL;
    l.init = fInit;
    l.affectation = fAffectation;
    l.affiche = fAffiche;
    l.compare = fCompare;
    l.testament = fTestament;
    l.nb_elem = 0;
}

void initListe(Liste & l1, const Liste & l2, bool verbose) {
    initListe(l1, l2.init, l2.affectation, l2.affiche, l2.compare, l2.testament);

    Cellule *tmp = premiereCellule(l2);
    if (tmp) {
        do {
            ajoutEnQueue(elementCellule(tmp), l1, verbose);
            tmp = celluleSuivante(tmp, l2);
        } while (tmp != premiereCellule(l2));
    }
}

void testamentListe(Liste & l, bool verbose) {
    videListe(l, verbose);
}

void affectation(Liste & l1, const Liste & l2) {
    testamentListe(l1);
    initListe(l1, l2);
}

void concat(Liste &l1, const Liste &l2, bool verbose) {
    Cellule *tmp = premiereCellule(l2);
    if (tmp) {
        do {
            ajoutEnQueue(elementCellule(tmp), l1, verbose);
            tmp = celluleSuivante(tmp, l2);
        } while (tmp != premiereCellule(l2));
    }
}

bool testListeVide(const Liste & l) {
    return ((l.nb_elem == 0) && (premiereCellule(l) == NULL));
}

Elem premierElement(const Liste & l) {
    return elementCellule(premiereCellule(l));
}

Cellule * premiereCellule(const Liste & l) {
    return l.ad;
}

Cellule * derniereCellule(const Liste & l) {
    return cellulePrecedente(premiereCellule(l));
}

Cellule * celluleSuivante(const Cellule *c) {
    return c->suivant;
}

Cellule * celluleSuivante(const Cellule *c, const Liste & l) {
    return c->suivant;
}

Cellule * cellulePrecedente(const Cellule *c) {
    return c->precedent;
}

Cellule * cellulePrecedente(const Cellule *c, const Liste &l) {
    return c->precedent;
}

Elem elementCellule(const Cellule * c) {
    return c->info;
}

void affichageListe(const Liste & l, bool complet) {
    if (testListeVide(l))
        cout << "la liste est vide\n";
    else if (complet) {
        cout << endl << endl << "=== affichage complet de la liste ==" << endl;
        Cellule *tmp = premiereCellule(l);
        cout << "nombre d'elements : " << l.nb_elem << endl;
        int i = 1;
        do {
            if (tmp == premiereCellule(l))
                cout << "Premier cellule :" << endl;
            else if (tmp == derniereCellule(l))
                cout << "Derniere cellule :" << endl;
            else
                cout << "cellule " << i << ":" << endl;

            cout << "\tadresse : " << tmp << endl;
            cout << "\telement : ";
            l.affiche(elementCellule(tmp));
            cout << endl << "\tprecedent : " << celluleSuivante(tmp) << endl;
            cout << "\tsuivant : " << cellulePrecedente(tmp) << endl;

            tmp = celluleSuivante(tmp, l);
            i++;
        } while (tmp != premiereCellule(l));

    } else {
        Cellule *tmp = premiereCellule(l);
        do {
            l.affiche(elementCellule(tmp));
            tmp = celluleSuivante(tmp, l);
        } while (tmp != premiereCellule(l));
        cout << endl;
    }
}

Cellule* rechercherElem(Liste &l, const Elem &e, bool verbose) {
    Cellule* tmp = premiereCellule(l);
    Cellule* prm = premiereCellule(l);

    if (tmp != NULL) {
        do {
            if (l.compare(e, elementCellule(tmp)) == 0) {
                return tmp;
            } else {
                tmp = celluleSuivante(tmp);
            }
        } while (tmp != prm);
        tmp = NULL;
    }

    return tmp;
}

void ajoutEnTete(const Elem & e, Liste & l, bool verbose) {
    Cellule *tmp = new Cellule;
    l.init(tmp->info, e, verbose);

    if (verbose) {
        cout << "element à rajouter" << endl;
        l.affiche(e);
        cout << "element de la cellule" << endl;
        l.affiche(elementCellule(tmp));
        cout << endl;
    }

    if (testListeVide(l)) {
        tmp->suivant = tmp;
        tmp->precedent = tmp;
        l.ad = tmp;
    } else {
        tmp->suivant = premiereCellule(l);
        tmp->precedent = cellulePrecedente(premiereCellule(l));
        l.ad->precedent->suivant = tmp;
        l.ad->precedent = tmp;
        l.ad = tmp;
    }
    l.nb_elem++;
}

void suppressionEnTete(Liste & l, bool verbose) {
    if (verbose)
        cout << endl;
    Cellule *tmp = premiereCellule(l);
    if (tmp->suivant == premiereCellule(l)) /* si il n'y a qu'une seule cellule */ {
        if (verbose)
            cout << "suppression de la dernière cellule" << endl;
        l.testament(tmp->info);
        delete premiereCellule(l);
        l.ad = NULL;
    } else {
        if (verbose)
            cout << "suppression de la " << l.nb_elem << "eme cellule" << endl;
        tmp->suivant->precedent = derniereCellule(l);
        tmp->precedent->suivant = celluleSuivante(tmp);
        l.ad = celluleSuivante(tmp);
        l.testament(tmp->info);
        delete tmp;
    }
    l.nb_elem--;
    if (verbose) {
        cout << "nombre d'elements " << l.nb_elem << endl;
        affichageListe(l, true);
    }
}

void videListe(Liste & l, bool verbose) {
    while (premiereCellule(l))
        suppressionEnTete(l, verbose);
}

void ajoutEnQueue(const Elem & e, Liste & l, bool verbose) {
    if (testListeVide(l)) {
        ajoutEnTete(e, l);
    } else {
        Cellule *tmp = new Cellule;
        l.init(tmp->info, e, verbose);
        tmp->suivant = premiereCellule(l);
        tmp->precedent = cellulePrecedente(premiereCellule(l));
        l.ad->precedent->suivant = tmp;
        l.ad->precedent = tmp;
        l.nb_elem++;
    }
}

void triPartition(const Liste &l, Liste &resultat) {
    //cout << "je suis passé par là" << endl;
    Liste inf, pivot, sup;
    initListe(inf, l.init, l.affectation, l.affiche, l.compare, l.testament);
    initListe(pivot, l.init, l.affectation, l.affiche, l.compare, l.testament);
    initListe(sup, l.init, l.affectation, l.affiche, l.compare, l.testament);
    //cout << "initialisations terminées"<<endl;
    separe(l, inf, pivot, sup);
    //cout << "liste séparée" << endl;
    if (!testListeVide(inf)) {
        //cout << "entrée de inf dans la fonction récursive" << endl;
        triPartition(inf, inf);
        //cout << "sortie de inf de la fonction récursive" << endl;
    }
    if (!testListeVide(sup)) {
        triPartition(sup, sup);
    }
    concat(inf, pivot);
    concat(inf, sup);
    affectation(resultat, inf);
    testamentListe(inf);
    testamentListe(pivot);
    testamentListe(sup);
}

void separe(const Liste &l, Liste &inf, Liste &pivot, Liste &sup, bool verbose) {
    Cellule *tmp = premiereCellule(l);

    if (tmp) {
        const Elem piv = elementCellule(tmp);
        do {
            if (l.compare(piv, elementCellule(tmp)) > 0)
                ajoutEnQueue(elementCellule(tmp), inf, verbose);
            else if (l.compare(piv, elementCellule(tmp)) < 0)
                ajoutEnQueue(elementCellule(tmp), sup, verbose);
            else
                ajoutEnQueue(elementCellule(tmp), pivot, verbose);
            tmp = celluleSuivante(tmp);
        } while (tmp != premiereCellule(l));
    }
}
